package com.jiang.专题.树.Q100;

import com.jiang.专题.树.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/09/04 16:56
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null) return p == q;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    // public boolean isSameTree(TreeNode p, TreeNode q) {
    //     List<Integer> p1 = pre(p);
    //     List<Integer> q1 = pre(q);
    //     // for (int i = 0; i < p1.size() && i < q1.size(); i++) {
    //     //     if (!Objects.equals(p1.get(i), q1.get(i))) {
    //     //         return false;
    //     //     }
    //     // }
    //     // return true;
    //     return p1.equals(q1);
    // }

    private List<Integer> pre(TreeNode node) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            TreeNode n = stack.pop();
            if (n != null) {
                res.add(n.val);
                stack.push(n.right);
                stack.push(n.left);
            } else {
                res.add(null);
            }
        }
        return res;
    }
}
